package bt2array

import (
	C "gitee.com/ljfirst/algo-go-sdk/common/constant"
	"gitee.com/ljfirst/algo-go-sdk/src/data_structure/heap_stack_queue/stack"
	"gitee.com/ljfirst/algo-go-sdk/src/data_structure/list"
)

/**
 * @author ljfirst
 * @version V1.0
 * @date 2023/7/23 00:11
 * @author-Email ljfirst@mail.ustc.edu.cn
 * @blogURL https://blog.csdn.net/ljfirst
 * @description
 **/
type PreOrderByStack2 struct {
	ans []int
}

func (m *PreOrderByStack2) Method(node *list.Node) []int {
	if node == nil {
		return nil
	}
	if len(m.ans) == 0 {
		m.ans = make([]int, 0)
	}
	stackTools := stack.ArrayStack{}
	for stackTools.Size() != 0 || node != nil {
		for node != nil {
			m.ans = append(m.ans, node.Value.(int))
			stackTools.Push(node)
			node = node.Left
		}
		//attention: 为什么不需要判断stack.isEmpty()？
		//因为while内仅有此处在pop，每次pop完都会被while循环判断一次
		//node不为空有业务逻辑，node为空则有Size判断
		node = stackTools.Pop().(*list.Node).Right
	}
	return m.ans
}

func (m *PreOrderByStack2) GetAttribute() *C.Attribute {
	return &C.Attribute{
		Tags: []string{C.Tree, C.PreOrder, C.Stack},
		Desc: &C.Desc{
			Name:        "PreOrderByStack2",
			NameCn:      "先序遍历",
			Description: "使用栈进行先序遍历",
			ParamsDesc: map[string]string{
			},
			Example: map[int]string{
			},
		},
	}
}
